package common

import (
	"errors"
	"hash/crc32"
	"sort"
	"strconv"
	"sync"
)

// 声明切片类型 (所有的hash节点)
// 实现排序接口
type uints []uint32

// 获取hash所有节点的长度
func (u *uints) Len() int {
	return len(*u)
}

// 比较两个数的大小 如果  i小于j 返回true
func (u *uints) Less(i, j int) bool {
	return (*u)[i] < (*u)[j]
}

// 交换两个值
func (u *uints) Swap(i,j int)  {
	(*u)[i],(*u)[j] = (*u)[j],(*u)[i]
}

// hash 环没有数据时提示错误
var errEmpty = errors.New("hash 环没有数据")

type Consistent struct {
	// hash 环 ,key为hash值,value为节点信息
	Circle map[uint32]string
	// 已经排序好的节点hash切片
	sortedHashes uints
	// 虚拟节点个数,用来增加hash的平衡性
	VirtualNode int
	// 读写锁
	sync.RWMutex
}

// 创建一致性hash算法结构体
func NewConsistent() *Consistent {
	return &Consistent{
		Circle: make(map[uint32]string),
		// 设置节点个数
		VirtualNode:  20,
	}
}

// 自动生成key值
func (c *Consistent) generateKey(element string, index int) string {
	// 副本生成key逻辑
	return element + strconv.Itoa(index)
}

// 根据key生成hash
func (c *Consistent) hashKey(key string) uint32 {
	if len(key) < 64 {
		var srcatch []byte
		srcatch = make([]byte,64)
		copy(srcatch,key)
		return crc32.ChecksumIEEE(srcatch)
	}
	return crc32.ChecksumIEEE([]byte(key))
}

func (c *Consistent) updateSortedHashes() {
	hashes := c.sortedHashes[:0]
	// 判断切片容量是否过大,如果过大重置
	if cap(c.sortedHashes)/(c.VirtualNode * 4) > len(c.Circle) {
		hashes = nil
	}
	// 添加hashes
	for k,_ := range c.Circle {
		hashes = append(hashes,k)
	}
	// 对所有节点hash进行排序
	// 方便之后进行二分查找
	sort.Sort(&hashes)
	// 重新赋值
	c.sortedHashes = hashes

}

// 向hash环增加节点
func (c *Consistent) Add(element string) {
	// 加锁
	c.Lock()
	defer c.Unlock()
	c.add(element)
}



// 在hash环上增加节点的副本节点
func (c *Consistent) add(element string) {
	for i := 0; i < c.VirtualNode; i++ {
		// 副本节点和hash值整到hash环中
		c.Circle[c.hashKey(c.generateKey(element,i))] = element
	}
	// 对写入的切片进行排序
	// 更新排序
	c.updateSortedHashes()
}

// 删除节点,删除当前节点的所有副本节点
func (c *Consistent) remove(element string) {
	for i := 0; i < c.VirtualNode; i++ {
		delete(c.Circle,c.hashKey(c.generateKey(element,i)))
	}
	// 删除后重新排序剩余节点
	c.updateSortedHashes()
}

// 删除节点
func (c *Consistent) Remove(element string) {
	// 加锁
	c.Lock()
	defer c.Unlock()
	c.remove(element)
}

// 根据数据获取最近的节点
func (c *Consistent) Get(uid string) (string, error) {
	// 添加读锁
	c.RLock()
	defer c.RUnlock()
	// 为空返回错误
	if len(c.Circle) == 0 {
		return "",errEmpty
	}
	// 计算hash值
	hashValue := c.hashKey(uid)
	i := c.search(hashValue)
	// 返回找到的节点
	return c.Circle[c.sortedHashes[i]],nil
}

// 顺时针查找下一个最近的节点
func (c *Consistent) search(hashValue uint32) int {
	// 查找算法  寻找最近的下一个hash节点 二分查找算法
	x := sort.Search(len(c.sortedHashes), func(i int) bool {
		// 如果节点大于则返回
		return c.sortedHashes[i] > hashValue
	})

	if x >= len(c.sortedHashes) {
		// 没找到
		return 0
	}
	return x

}